{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Money Required Before Transactions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumMoney"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #完成所有交易的初始最少钱数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code><font face=\"monospace\">transactions</font></code>，其中<code>transactions[i] = [cost<sub>i</sub>, cashback<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>数组描述了若干笔交易。其中每笔交易必须以 <strong>某种顺序</strong> 恰好完成一次。在任意一个时刻，你有一定数目的钱&nbsp;<code>money</code>&nbsp;，为了完成交易&nbsp;<code>i</code>&nbsp;，<code>money &gt;= cost<sub>i</sub></code>&nbsp;这个条件必须为真。执行交易后，你的钱数&nbsp;<code>money</code> 变成&nbsp;<code>money - cost<sub>i</sub> + cashback<sub>i</sub></code><sub>&nbsp;</sub>。</p>\n",
    "\n",
    "<p>请你返回 <strong>任意一种</strong> 交易顺序下，你都能完成所有交易的最少钱数<em>&nbsp;</em><code>money</code>&nbsp;是多少。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>transactions = [[2,1],[5,0],[4,2]]\n",
    "<b>输出：</b>10\n",
    "<strong>解释：\n",
    "</strong>刚开始 money = 10 ，交易可以以任意顺序进行。\n",
    "可以证明如果 money &lt; 10 ，那么某些交易无法进行。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>transactions = [[3,0],[0,3]]\n",
    "<b>输出：</b>3\n",
    "<strong>解释：</strong>\n",
    "- 如果交易执行的顺序是 [[3,0],[0,3]] ，完成所有交易需要的最少钱数是 3 。\n",
    "- 如果交易执行的顺序是 [[0,3],[3,0]] ，完成所有交易需要的最少钱数是 0 。\n",
    "所以，刚开始钱数为 3 ，任意顺序下交易都可以全部完成。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= transactions.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>transactions[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= cost<sub>i</sub>, cashback<sub>i</sub> &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-money-required-before-transactions](https://leetcode.cn/problems/minimum-money-required-before-transactions/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-money-required-before-transactions](https://leetcode.cn/problems/minimum-money-required-before-transactions/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,1],[5,0],[4,2]]', '[[3,0],[0,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        tmp1 = []\n",
    "        tmp2 = []\n",
    "        M = -1\n",
    "        M2 = -1\n",
    "        m = -1\n",
    "        for x, y in transactions:\n",
    "            if x > y:\n",
    "                m = max(m, y)\n",
    "                tmp1.append([x, y])\n",
    "            else:\n",
    "                M2 = max(x, M2)\n",
    "                tmp2.append([x, y])\n",
    "            M = max(x, M)\n",
    "        \n",
    "        # tmp1.sort(key = lambda x: (x[1], -x[0]))\n",
    "        # print(transactions)\n",
    "        if M2 == -1:\n",
    "            s = 0\n",
    "        else:\n",
    "            s = M2\n",
    "        for x, y in tmp1:\n",
    "            s += x - y\n",
    "        if M2 == -1:\n",
    "            s += m\n",
    "        else:\n",
    "            if m > M2:\n",
    "                s += m - M2\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, t: List[List[int]]) -> int:\n",
    "        n = len(t)\n",
    "        # delta = [x2 - x1 for x1, x2 in t]\n",
    "        t.sort(key=lambda x: x[1])\n",
    "        pos = [x for x in t if x[1] - x[0] < 0]\n",
    "        neg = [x[0] for x in t if x[1] - x[0] >= 0]\n",
    "        # print(t)\n",
    "        # print(pos)\n",
    "        # print(neg)\n",
    "        ans = 0\n",
    "        re = 0\n",
    "        for x, y in pos:\n",
    "            if re < x:\n",
    "                ans += x - re\n",
    "                re = x\n",
    "            re -= x\n",
    "            re += y\n",
    "        return ans + max((max(neg) if neg else 0) - re, 0)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        totalLose = 0\n",
    "        max_cost = 0\n",
    "        max_back = 0\n",
    "        for cost,back in transactions:\n",
    "            if cost>back:\n",
    "                totalLose += (cost - back)\n",
    "                max_back = max(max_back, back)\n",
    "            else:\n",
    "                max_cost = max(max_cost, cost)\n",
    "        return totalLose + max(max_cost, max_back)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        # 考虑最严苛的情况，应该先完成所有亏钱的交易，完成亏钱交易的最严苛的情况是最后完成cashback最大的交易\n",
    "        # 然后完成赚钱的交易，完成赚钱的交易最严苛的情况是先完成cost最大的交易\n",
    "        ans = 0\n",
    "        MX = 0\n",
    "        for cost, cashback in transactions:\n",
    "            ans += max(cost - cashback, 0)\n",
    "            MX = max(min(cashback, cost), MX)\n",
    "        return ans + MX"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total_lose = mx = 0\n",
    "        for cost, cashback in transactions:\n",
    "            total_lose += max(cost - cashback, 0)\n",
    "            mx = max(mx, min(cost, cashback))\n",
    "        return total_lose + mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        m = max([x for x, y in transactions if x <= y], default=0)\n",
    "        a = [[x, y] for x, y in transactions if x > y]\n",
    "        a.sort(key=itemgetter(1))\n",
    "\n",
    "        def f(k):\n",
    "            for x, y in a:\n",
    "                if k < x:\n",
    "                    return -1\n",
    "                k += y - x\n",
    "            return k\n",
    "\n",
    "        lo, hi = 0, int(1e18)\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi) // 2\n",
    "            if f(mid) >= 0:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "\n",
    "        return lo + max(m - f(lo), 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        # 两种\n",
    "        # 第一种：亏钱\n",
    "        # 第二种：不亏不赚或者赚钱\n",
    "        # 最费钱的策略：先亏完再赚\n",
    "        # 保证赚钱的时候本金充裕：所有亏钱交易完成后还有本金去赚钱\n",
    "\n",
    "        # 亏钱：\n",
    "\n",
    "\n",
    "        max_cost_p = 0\n",
    "        n_list = []\n",
    "        # max_cost_n = 0;\n",
    "        max_back_n = 0\n",
    "        total_n = 0\n",
    "\n",
    "        for item in transactions:\n",
    "            if item[1]-item[0]>=0:\n",
    "                if item[0]>max_cost_p:\n",
    "                    max_cost_p = item[0]\n",
    "\n",
    "            if item[1]-item[0]<0:\n",
    "                if item[1]>max_back_n:\n",
    "                    # total_n = total_n+ max_cost_n-max_back_n\n",
    "                    # max_cost_n = item[0]\n",
    "                    max_back_n = item[1]\n",
    "                total_n = total_n+ item[0]-item[1]\n",
    "\n",
    "        \n",
    "        # if max_back_n>max_cost_p:\n",
    "        #     max_cost_p = max_cost_p + max_cost_n-max_back_n\n",
    "        # else:\n",
    "        #     max_cost_p = max_cost_n\n",
    "\n",
    "        return max(max_cost_p,max_back_n)+total_n\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        neg_sum = 0\n",
    "        ret = 0\n",
    "        for pr in transactions:\n",
    "            if pr[0] > pr[-1]: neg_sum += pr[0] - pr[-1]\n",
    "        for pr in transactions:\n",
    "            if pr[0] > pr[-1]: neg_sum -= pr[0] - pr[-1]\n",
    "            ret = max(ret, neg_sum + pr[0])\n",
    "            if pr[0] > pr[-1]: neg_sum += pr[0] - pr[-1]\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total = mx = 0\n",
    "        for cost, cashback in transactions:\n",
    "            total += max(cost - cashback, 0)\n",
    "            if cashback <= cost:\n",
    "                mx = max(mx, cashback)\n",
    "            if cashback >= cost:\n",
    "                mx = max(mx, cost)\n",
    "            #print(mx)\n",
    "        return total + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total_lose = mx = 0\n",
    "        for cost,cashback in transactions:\n",
    "            if cost >= cashback:\n",
    "                total_lose += cost - cashback\n",
    "                if cashback > mx:mx = cashback\n",
    "            elif cost > mx:\n",
    "                mx = cost\n",
    "        return total_lose + mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        s = sum(cos - cash for cos, cash in transactions if cos > cash)\n",
    "        ans = 0\n",
    "        for cos, cash in transactions:\n",
    "            if cos > cash:\n",
    "                cur = s - (cos-cash) + cos\n",
    "            else:\n",
    "                cur = s + cos\n",
    "            if cur > ans:\n",
    "                ans = cur\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, a: List[List[int]]) -> int:\n",
    "        k1,k2=0,0\n",
    "        for i,j in a:\n",
    "            k1+=max(0,i-j)\n",
    "            k2=max(k2,min(i,j))\n",
    "        return k1+k2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        need = 0\n",
    "        M = 0\n",
    "        for c, cb in transactions:\n",
    "            need += max(0, c - cb)\n",
    "            if c > cb:\n",
    "                M = max(M, cb)\n",
    "            else:\n",
    "                M = max(M, c)\n",
    "        return M + need"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        tot = mx = 0\n",
    "        for cost,cashback in transactions:\n",
    "            if cost > cashback: # 亏钱\n",
    "                tot += cost-cashback\n",
    "                if cashback > mx:\n",
    "                    mx = cashback\n",
    "            elif cost > mx: # 赚钱\n",
    "                mx = cost\n",
    "        return tot+mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total_lose = mx = 0\n",
    "        for cost, cashback in transactions:\n",
    "            total_lose += max(cost - cashback, 0)\n",
    "            mx = max(mx, min(cost, cashback))\n",
    "        return total_lose + mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "                n = len(transactions)\n",
    "                ans = s = 0\n",
    "                \n",
    "                for i,j in transactions:\n",
    "                    if i > j:\n",
    "                        s += i - j\n",
    "                for i,j in transactions:\n",
    "                    t = s\n",
    "                    if i > j:\n",
    "                        t -= i - j\n",
    "                    ans = max(ans,t + i)\n",
    "                return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        neg = 0\n",
    "        for a,b in transactions:\n",
    "            if a>b:\n",
    "                neg += b-a\n",
    "        ans = 0\n",
    "        for a,b in transactions:\n",
    "            if a>b:\n",
    "                ans = max(ans, -neg -(a-b)+a)\n",
    "            else:\n",
    "                ans = max(ans, -neg + a)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        # 所有交易顺序都能完成交易\n",
    "        # 什么是最差情况？ 前进行亏的交易\n",
    "        ans = 0\n",
    "        lose = 0\n",
    "        for c, b in transactions:\n",
    "            lose += max(0, c - b)\n",
    "        for c, b in transactions:\n",
    "            if c > b:\n",
    "                ans = max(ans, lose - (c - b) + c)\n",
    "            else:\n",
    "                ans = max(ans, lose + c)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total_lose = mx = 0\n",
    "        for cost, cashback in transactions:\n",
    "            total_lose += max(cost - cashback, 0)\n",
    "            mx = max(mx, min(cost, cashback))\n",
    "        return total_lose + mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total_lose = mx = 0\n",
    "        for cost, cashback in transactions:\n",
    "            total_lose += max(cost - cashback, 0)\n",
    "            mx = max(mx, min(cost, cashback))\n",
    "        return total_lose + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        tot = mx = 0\n",
    "        for cost,cashback in transactions:\n",
    "            if cost > cashback: # 亏钱\n",
    "                tot += cost-cashback\n",
    "                if cashback > mx:\n",
    "                    mx = cashback\n",
    "            elif cost > mx: # 赚钱\n",
    "                mx = cost\n",
    "        return tot+mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, a: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        c=0\n",
    "        for i,j in a:\n",
    "            if i>j:\n",
    "                c+=i-j\n",
    "        for i,j in a:\n",
    "            if i>j:\n",
    "                ans=max(ans,c+j)\n",
    "            else:\n",
    "                ans=max(ans,c+i)\n",
    "            ans=max(ans,c)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total_lose = mx = 0\n",
    "        for cost,cashback in transactions:\n",
    "            if cost >= cashback:\n",
    "                total_lose += cost - cashback\n",
    "                if cashback > mx:mx = cashback\n",
    "            elif cost > mx:\n",
    "                mx = cost\n",
    "        return total_lose + mx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        tl=0\n",
    "        mx=0\n",
    "        for c,b in transactions:\n",
    "            if b<c:\n",
    "                tl+=c-b \n",
    "                mx=max(mx,b)\n",
    "            else:\n",
    "                mx=max(mx,c)\n",
    "        return tl+mx\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        totalLose = mx = 0\n",
    "        for cost,back in transactions:\n",
    "            totalLose += max(0,cost - back)\n",
    "            mx = max(mx, min(cost, back))\n",
    "        return totalLose + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\r\n",
    "        # total_lose为亏损情况，mx为最大启动资金\r\n",
    "        total_lose = mx = 0  \r\n",
    "        for cost, cashback in transactions:\r\n",
    "            total_lose += max(cost - cashback, 0)\r\n",
    "            mx = max(mx, min(cost, cashback))\r\n",
    "        return total_lose + mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        transactions.sort(key=lambda x:x[1]-x[0])\n",
    "        index=0\n",
    "        res=0\n",
    "        s=0\n",
    "        while index<len(transactions) and transactions[index][1]-transactions[index][0]<0:\n",
    "            s+=(transactions[index][1]-transactions[index][0])\n",
    "            index+=1\n",
    "        for i in range(0,index):\n",
    "            # print(i, res)\n",
    "            res=max(res, transactions[i][0]-1*(s-(transactions[i][1]-transactions[i][0])))\n",
    "        # print(transactions,s,res)\n",
    "        if index<len(transactions):\n",
    "            res+=max(0, max([x[0] for x in transactions[index:]])-(res+s))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        need = 0\n",
    "        M = 0\n",
    "        for ct, c in transactions:\n",
    "            if ct > c:\n",
    "                need += ct - c \n",
    "                M = max(M, c)\n",
    "            else:\n",
    "                M = max(M, ct)\n",
    "        return need + M"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        mx_back, mx_cost, money = 0, 0, 0\n",
    "        for cost, back in transactions:\n",
    "            if back < cost:\n",
    "                money += cost - back\n",
    "                if back > mx_back:\n",
    "                    mx_back = back\n",
    "            else:\n",
    "                if cost > mx_cost:\n",
    "                    mx_cost = cost\n",
    "        return money + max(mx_cost, mx_back)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        \n",
    "        def check(it):\n",
    "            cos, cash = it[:]\n",
    "            if cos > cash:\n",
    "                return [-1, cash]\n",
    "            return [1, -cos]\n",
    "        transactions.sort(key=check)\n",
    "        ans = pre=  0\n",
    "        for a, b in transactions:\n",
    "            if pre < a:\n",
    "                ans += a-pre\n",
    "                pre = a\n",
    "            pre += -a+b\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        maxPos = accuNeg = res = 0\n",
    "        for cost, cash in transactions:\n",
    "            if cost <= cash:\n",
    "                maxPos = max(maxPos , cost)\n",
    "            else:\n",
    "                accuNeg += cost - cash\n",
    "        res = maxPos + accuNeg\n",
    "        for cost, cash in transactions:\n",
    "            if cost > cash:\n",
    "                res = max(res, accuNeg - (cost - cash) + max(maxPos, cost))\n",
    "        return res\n",
    "        \n",
    "            \n",
    "\n",
    "        maxCost = accuDec = maxNegCost = maxNegCash = 0\n",
    "        for cost, cash in transactions:\n",
    "            maxCost = max(maxCost, cost)\n",
    "            if cost <= cash: continue\n",
    "            accuDec += cost - cash\n",
    "            if cost < maxNegCost: continue\n",
    "            if cost > maxNegCost:\n",
    "                maxNegCost = cost\n",
    "                maxNegCash = cash\n",
    "            else:\n",
    "                maxNegCash = max(maxNegCash, cash)\n",
    "        return maxCost + accuDec - (maxNegCost - maxNegCash)\n",
    "\n",
    "\n",
    "        # x - y >= max(remain costs)\n",
    "\n",
    "           \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        transactions.sort(key=lambda x:x[1]-x[0])\n",
    "        index=0\n",
    "        res=0\n",
    "        s=0\n",
    "        while index<len(transactions) and transactions[index][1]-transactions[index][0]<0:\n",
    "            s+=(transactions[index][1]-transactions[index][0])\n",
    "            index+=1\n",
    "        for i in range(0,index):\n",
    "            # print(i, res)\n",
    "            res=max(res, transactions[i][0]-1*(s-(transactions[i][1]-transactions[i][0])))\n",
    "        # print(transactions,s,res)\n",
    "        if index<len(transactions):\n",
    "            res+=max(0, max([x[0] for x in transactions[index:]])-(res+s))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        delta = [c - b for c, b in transactions]\n",
    "        s = sum(x for x in delta if x > 0)  # 所有亏损的交易额之和\n",
    "        ans = 0\n",
    "        n = len(transactions)\n",
    "        for i in range(n):\n",
    "            c, b = transactions[i]\n",
    "            if c - b > 0:\n",
    "                ans = max(ans, s - (c - b) + c)\n",
    "            else:\n",
    "                ans = max(ans, s + c)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total = sum(b - a for a, b in transactions if b - a < 0)\n",
    "        ans = total - max([a for a, b in transactions if b - a >= 0] + [0])\n",
    "        for a, b in transactions:\n",
    "            if b - a < 0:\n",
    "                ans = min(ans, total - b)\n",
    "        return -ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        tot = sum([max(cost-cash, 0) for cost, cash in transactions])\n",
    "        ans = 0\n",
    "        for cost, cash in transactions:\n",
    "            if cost > cash:\n",
    "                ans = max(ans, tot+cash)\n",
    "            else:\n",
    "                ans = max(ans, tot+cost)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        tt = []\n",
    "        dif = [j-i for i,j in transactions]\n",
    "        ili = []\n",
    "        jli = []\n",
    "        for k in range(len(dif)):\n",
    "            if dif[k] < 0:\n",
    "                ili.append(transactions[k][0])\n",
    "                jli.append(transactions[k][1])\n",
    "            else:\n",
    "                tt.append(transactions[k])\n",
    "        if not ili:\n",
    "            return sorted(tt)[-1][0]\n",
    "        if not tt:\n",
    "            return sum(ili)-(sum(jli)-max(jli))\n",
    "        else:\n",
    "            return max(sum(ili)-(sum(jli)-max(jli)),sum(ili)-sum(jli)+sorted(tt)[-1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total = sum(b - a for a, b in transactions if b - a < 0)\n",
    "        ans = total - max([a for a, b in transactions if b - a >= 0] + [0])\n",
    "        for a, b in transactions:\n",
    "            if b - a < 0:\n",
    "                ans = min(ans, total - b)\n",
    "        return -ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoney(self, transactions: List[List[int]]) -> int:\n",
    "        total = sum(b - a for a, b in transactions if b - a < 0)\n",
    "        ans = total - max([a for a, b in transactions if b - a >= 0] + [0])\n",
    "        for a, b in transactions:\n",
    "            if b - a < 0:\n",
    "                ans = min(ans, total - b)\n",
    "        return -ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
